There are two basic models used for creating a queue. They are commonly known as the bank line model and the grocery line model because of their use in these industries. The bank line model employs a single queue that is serviced by a plurality of service providers. In this model the queue advances by one each time a service provider becomes available and the first request in the queue is assigned to the newly available service provider. The time that a request resides in the queue is a function of the service times for all of the requests that are in front of it in the queue. This model of queuing is functionally known as a “pull” model whereby service requests are pulled from the queue when they can be fulfilled.
The grocery store model, on the other hand, employs a queue for each service provider. This model of queuing employs a “push” model of assignment whereby requests are assigned to a queue associated with each service provider. Generally there is a control mechanism associated with such queues that tries to estimate the time required to fulfill the tasks in each queue. This information is then fed into an optimisation scheme to determine to which queues service requests should be assigned. The time required for service in the grocery store model is quite variable due to the possibility of entering a queue where all of the requests that are ahead in the queue are serviced quite quickly or the possibility that one or more of the requests in the queue require considerable time to be serviced. In general the time required to fill a request in the bank line model is considerably less variable, but not necessarily less, because every request in the queue is dependant on the time required for each request being served ahead of it. There are no “faster” queues in this model. A disadvantage in either model is the possibility of a request being serviced by a provider that is not well suited for the request.
The above discussion of queuing models should now be brought into the context of information retrieval systems where requests for information are presented to a plurality of servers or mechanisms operating thereon that are capable of providing the requested information. The queues used in such information retrieval systems are often more refined derivatives of the basic queuing models presented above with the refinements reflecting the desire for improved efficiency and an optimization of the method of dealing with requests from a particular client type or requesting information of a particular type.
The servers and mechanisms operating thereon used for the delivery of information are often arranged in two tiers. The first tier generally contains a mechanism that interfaces between a source of service requests and the servers of the second tier. The first tier also contains a mechanism that manages the assignment of requests to the second tier servers. Second tier servers that supply the information requested in service requests are referred to as query servers. A first tier server further will contain a queue (first tier queue) which holds service requests prior to them being distributed to a query server. The distribution of requests contained in the first tier queue to query servers can take place by one of two methods; they can be “pushed” by the first tier server on to a server of the second tier or they can be “pulled” from the first tier server by a server of the second tier, which can be either a query server or a server that manages a group of query servers. These two basic methods of assigning requests have advantages and disadvantages that at least in part reflect the nature of client requests being serviced. Both of these strategies require a first tier server that manages the assignment of service requests and maintains a queue that holds service requests prior to their distribution to query servers.
The “push” model of assigning requests to a server generally uses a two tier queue model. Service requests are queued in the first tier queue until they are assigned to a query server where they will be queued again. There are numerous approaches to assigning a request to a query server which generally rely on some form of server management. In one case the server that maintains the “main” queue, or an associated control server, maintains data on the response time required for query servers to fulfill service requests. This data, or calculations based on it, is used by the server of the first tier when assigning requests to query servers. The process aims to minimise the response time for a given service request. However, the ability to predict the time required for a given query server to fulfill a newly assigned service request is never completely accurate, casting doubt on the usefulness of the exercise. Yin another “push” model service requests are assigned to servers according to the request “type”. Service requests are assigned to a query server if that server is currently servicing requests of the same type. If there are no servers currently fulfilling service requests of the same type as the request about to be assigned to a query server the requests is assigned based on the above or similar server management considerations.
A second model for the assignment of requests in a queue is the “pull” model. The pull model also employs a two tier arrangement of servers. The level of server management that is required for the assignment of service requests is quite a bit lower than with the “push” model. Servers of the second tier simply indicate that they are ready to accept another service request instead of a control server requesting status updates for the second tier servers to determine their current request load.
In U.S. Pat. No. 6,023,722, Coyler presents a “pull” queue model that is applied to servicing of information requests from the World Wide Web. There is only one queue, associated with the first tier server, in the system presented in this patent. A queue at the second tier servers is not necessary as a new service request is only assigned to a second tier server once the server has completed the previous request and has indicated that it is ready to process another request. It is indicated that this model of assigning information requests to server of the second tier is more efficient because the server managing the main queue does not have to continually query the second tier servers to determine their current status.
Business Intelligence (BI) applications are often focussed on the production and editing of complex reports that are based on information contained in a data warehouse. The manipulation (including editing and authoring) of such reports involves multiple requests for data from a database. Thus the manipulation of such reports requires multiple requests to the database or data warehouse to obtain the required information. These multiple requests are often included in the same general query to the data warehouse. For example, the results of a query request are usually presented in pages, typically, of say 10 rows of data per page, with an individual service request being required to return each of these query pages.
It is the nature of contemporary database systems that information requests to a database usually involve a query preparation stage followed by a stage where rows of data are retrieved. Most of the data processing associated with a request to a database is generally performed in the query preparation stage (e.g. all rows of data identified in the query may need to be sorted). Thus, in cases of a plurality of requests within a single query the resources (and cost) associated with the first request of a query are often considerably higher than those associated with later requests against the same query. These later requests will only need to retrieve a fixed number of additional rows and not perform the preparatory work associated with the query.
Editing of business intelligence reports is also enabled by server requests which retrieve “metadata” or descriptions of the underlying reports themselves for the client to modify or apply modifications to those report definitions to a persistent store of reports. The query servers in this application provide the database access and document formatting necessary to create these reports dynamically based upon requests from the clients. Any activity of sufficient complexity or which needs to access centralized resources would benefit from a client-server architecture that reflects the above use of multiple requests within a single query.
There is a need for a system and method of providing information from a database to queries to the database that contain numerous service requests. The system and method should consider efficiencies related to the provision of information to closely related requests within a single query.